準備出遊，6.2 的 Raft 之後再補

5.3 提到 state machine replication（SMR）需要 total order broadcast。
而前面也提到，達到 total order broadcast 的其中一種方法，
可以透過 leader 決定訊息順序，並使用 FIFO broadcast 給其他節點。
問題在於 leader 掛掉時，要怎麼辦？

• manual failover：leader 掛掉的話，把負責的人摳爆，叫他重啟或是重選一個 leader。

如果轉換 leader 的工作靠手動，
除了員工不爽，還可能會導致服務不能用一陣子，
那有沒有自動的方法呢？
就是接下來介紹的 Consensus 共識演算法。

6.1 Intro to consensus

分散式系統中的節點要達到共識（Consensus），也就是都同意某個值。
一個或多個節點會 提議（propose） 一個數值，
然後透過共識演算法決定要採用哪個，
最後每個節點都達到一致，
而且決定好之後就不會改變心意～

Consensus 與 total order broadcast

consensus 跟 total order broadcast 可以互相轉換。

• total order broadcast -> consensus: 想要提議數值的節點就廣播，而 total order 決定 deliver 的第一個訊息當作大家同意的值。
• consensus -> total: 使用不同輪的 consensus 決定第一、二、三個要 deliver 的數值，想要廣播的節點就在這幾輪 consensus 中提議新數值，共識演算法會確保每個節點都同意這個 deliver 的訊息序列。（講得有點複雜ＱＱ 就是用 consensus 來做 total order，如果每次大家都同意一個數值，那每個節點 deliver 訊息的順序也就一樣）

目前有名的共識演算法:
Paxos、Multi-paxos
Raft

Consensus system models

共識演算法基於 partially sync, crash recovery system model

為什麼不用 async model?

• FLP result
  這個理論證明，如果假設 async model，沒有 deterministic 的共識演算法能保證會停下來。

• Paxos、Raft 等演算法只有在 timeout/failure detector 上用到 clock（確保 progress），在 correctness(safety) 上並不依賴時間。

Leader election

共識演算法的核心基本上就是發現舊的 leader 掛掉時，
能自動選上新的 leader。
而且要避免 split-brain：同時間有不只一個 leader，各說各話。

leader election 過程會根據不同演算法有所差異，
基本上是當節點有一陣子沒收到 leader 的訊息，
會發起選舉，成為 candidate，並問其他節點是否投票，
當有足夠 quorum 數量的節點投票，他就成為新的 leader。

Raft 演算法中，一個 term 只會有一個 leader，
但不同 term 可以有不同 leader，
之後會說明。

能保證同時間只有一個 leader？

我們需要避免 split-brain，
但基於一開始的假設：partially syncronus，
會因為 timeout 就判定舊的 leader 掛了、選出新 leader。
但或許只是網路真的很爛而已，
舊 leader 活著、甚至不知道自己被奪權了。

雖然不可能保證同時間有好幾個 leader，
但可以保證 每個 term 只有一個 leader。
Raft 中的 term 代表這是第幾次選舉 的 leader，
就是為了能夠做出區別。

每次決定下一個訊息的順序，leader 都要先問

這是一個很重視團隊意見的 leader XD
每次 leader 要決定下一個訊息，
就要獲得 quorum ，也就是大部分節點要同意。
以避免實際上有好幾個 leader（例如因為暫時的網路斷掉，已經有較大 term 的 leader 被選出）造成了節點間訊息順序不一致。

1. leader 詢問大家：can i deliver message m in term t?
2. 因為其他 follower 還沒有認識別的擁有更大 term 的 leader，就說好哇好哇聽你的，leader 獲得 quorum 投票
3. leader 叫大家 deliver m

6.2 Raft

Raft 演算法的部分會在我出去玩回來，也就是下禮拜之後補上